The Border Gateway Protocol, or BGP, is an inter-domain routing protocol used to exchange routing information among network devices (i.e., routers) in the same or in different autonomous systems (AS). An AS is one or more networks under control of a common administration entity and having common routing policies. A BGP network device is a computing system that runs the Border Gateway Protocol. Neighbor BGP network devices, also referred to as BGP peers, establish a transport protocol connection with each other, exchange messages to open a BGP session, and then exchange their entire routing information (i.e., routing table). In general, this routing information includes the complete route to each network destination reachable from a BGP network device. Each route comprises a destination address and information that describes the path to the address destination.
Typically, an address prefix represents the destination address in a given route. This address prefix includes a network address combined with a mask that indicates how many bits of the network address serve to identify the network. The remaining bits of the address prefix are available to represent network devices within that network. The path to the address destination (described within a given route) includes an Origin attribute, an AS_Path attribute, and a Next_Hop attribute. The Origin attribute indicates the means by which a BGP network device learned of the route. The AS_Path attribute provides a list of autonomous systems for reaching the address destination. The autonomous systems appear in the AS_Path in the order of their traversal. The Next_Hop attribute provides the address of the next hop (i.e., network device) towards the address destination.
Throughout an established BGP session, BGP peers maintain their routing information by exchanging incremental updates, such as the advertisement of new routes or withdrawals of existing routes. In general, BGP peers use update messages to exchange changes to the routing information. A BGP update message includes a message header, an Unfeasible Routes Length field, a Withdrawn Routes field, a Total Path Attribute Length field, a Path Attributes field, and a Network Layer Reachability Information (NLRI) field. The Unfeasible Routes Length field indicates the length of the Withdrawn Routes field. The Withdrawn Routes field indicates the address prefixes of routes being withdrawn from service. The Total Path Attribute Length field indicates the length of the Path Attributes field. The Path Attributes field provides the attributes, e.g., the Next_Hop attribute, Origin Attribute, and the AS_Path attribute, of each route being advertised in the BGP update message. The NLRI field provides the address field of each feasible route being advertised in the BGP update message.
Each BGP network device maintains the routes within a routing table. When a BGP network device advertises a reachable route or determines that a particular address destination is now unreachable, it sends update messages to its peers so that the peers may update their own routing tables. The time expended for a BGP network device to distribute the contents of its routing table (or updates of its routing table) to its BGP peers is referred to as convergence time. When the BGP network device has a large number of peers (e.g., more than 200) and a large number of routes (e.g., 100,000 or more) in its routing table, convergence can be a relatively slow process (in the order of several minutes). During a slow convergence, the end user can undergo degraded quality of experience because of latency, loss of packets, unreachable destinations, and packets received out of order.
In recognition of this problem, industry has devised different types of mechanisms to reduce convergence time. One type of mechanism, illustrated in FIG. 1, uses peer-groups 14-1, 14-2, 14-n (generally, 14). Currently, there are two forms of peer-groups: static peer-groups and dynamic update peer-groups.
For static peer-groups, each peer-group 14 includes one or more BGP peers 16, up to a defined maximum number. To be in the same peer-group, each member BGP peer 16 must have the same outbound routing policies. For instance, the BGP peers 16-1, 16-2, 16-3, and 16-4 of the peer-group 14-1 have the same outbound routing policies. In general, a routing policy determines how a given BGP network device 16 processes inbound and outbound routes. In many instances, a routing policy operates to filter routes, accept routes, accept and modify routes, and reject routes. Setting a routing policy for a BGP network device generally involves configuration by a network operator (e.g., through a CLI (command line interface)). Known mechanisms for configuring a routing policy for a BGP device include, but are not limited to, one or more of the following mechanisms: access lists, filter lists, prefix lists, prefix trees, and route maps.
Referring to FIG. 1, each static peer-group 14 having more than one BGP peer includes a master device. For example, BGP device 16-1 is the master device of peer-group 14-1, BGP device 16-5 is the master device of peer-group 14-2, and BGP device 16-6 is the master device of peer-group 14-3.
Consider another BGP network device 12, which learns of a new route or withdrawal of an existing route and is in communication with each group master. By sending update messages to group masters only, the BGP network device 12 produces fewer update messages than if it sent such messages to all of its BGP peers 16, thus accelerating convergence. The BGP network device 12 walks through its BGP routing table for each group master only, filters the address prefixes through the outbound policies of the group masters, generates update messages 22, and sends the update messages 22 to the group masters. Each group master replicates its received update messages 22 and sends them to the other peer devices 16 in their respective static peer-group 14.
The requirement that all peers in the same peer-group must have the same outbound routing policy is, however, a limitation that can lead a network operator to configure small BGP peer-groups, which reduces the efficiency of update message generation. Another limitation is that every BGP device 16 in the same peer-group 14 must belong to the same address family.
In recognition of the limitations of static peer-group configurations, industry produced dynamic update-peer groups. Dynamic update peer-groups separate BGP update message generation from peer-group configuration. For instance, BGP peers sharing the same outbound routing policy that are not members of a peer-group can become members of an update peer-group. This mechanism dynamically calculates BGP update group membership based on outbound routing policies, automatically and independently, and, unlike static peer-groups, requires no configuration by the network operator. In addition, outbound routing policies no longer restrict BGP neighbor configuration, and update peer-groups can belong to different address families. A limitation, however, is that the BGP network device must recalculate update-group membership upon every implementation of or change to an outbound routing policy.